package demo.practice.competition;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class P5793_2 {

    /**
     * [[".","+"]]
     * [0,0]
     *
     * @param args
     */

    public static void main(String[] args) {
        P5793_2 p5793_2 = new P5793_2();
        int i = p5793_2.nearestExit(new char[][]{{'.', '+'}}, new int[]{0, 0});
        System.out.println(i);
    }

    public int nearestExit(char[][] maze, int[] entrance) {
        int[][] vt = new int[maze.length][maze[0].length];
        Trie t = new Trie();
        t.insert(maze, entrance[0], entrance[1], t, vt);
        return t.getHeight();
    }

    static class Trie {
        Map<Character, Trie> child = new HashMap<>();
        boolean isend;

        public void insert(char[][] maze, int i, int j, Trie cur, int[][] vt) {
            if (getHeight() != -1)
                return;
            //Trie cur = this;
            if (i >= 0 && i < maze.length && j >= 0 && j < maze[i].length) {
                if (maze[i][j] == '+' || vt[i][j] == 0)
                    return;

                if (!cur.child.containsKey('.')) {
                    cur.child.put('.', new Trie());
                }


                vt[i][j]=1;
                insert(maze, i + 1, j, cur.child.get('.'), vt);
                insert(maze, i - 1, j, cur.child.get('.'), vt);
                insert(maze, i, j + 1, cur.child.get('.'), vt);
                insert(maze, i, j - 1, cur.child.get('.'), vt);
            } else {
                cur.isend = true;
            }
        }

        public int getHeight() {
            Trie cur = this;
            int height = 0;
            while (cur != null) {
                if (cur.child.containsKey('.')) {
                    Trie ch = cur.child.get('.');
                    if (ch != null && ch.isend && height > 0)
                        return height;
                    else {
                        cur = ch;
                        height++;
                    }
                } else {
                    return -1;
                }
            }
            return -1;
        }

    }
}
